Metadata for a virtual machine (VM) contains information such as the name, description, and configuration data for the VM. When a VM is created/instantiated on a host machine, the VM requests for metadata associated with the VM from a metadata server (often through a metadata proxy server). With the number of virtual machines that may operate in a multi-tenant data center, each tenant's network topology may include several different subnets with different IP address ranges assigned to these subnets. As such, two or more subnets (belonging to different tenants) may share the same or overlapping IP address ranges. Typically, in order to provide metadata proxy services for different logical networks that have subnets with overlapping IP address ranges, a network has to deploy multiple metadata proxy servers that are isolated from each other. As such, a large network that implements thousands of logical networks would require thousands of isolated metadata proxy servers.